Max-Heap এবং Min-Heap এর ইমপ্লিমেন্টেশন

Max-Heap এবং Min-Heap এর ইমপ্লিমেন্টেশন

Max-Heap এবং Min-Heap দুটি আলাদা হিপ গঠন। Max-Heap-এ প্রতিটি নোডের মান তার সন্তানের মানের থেকে বড় হয়, আর Min-Heap-এ প্রতিটি নোডের মান তার সন্তানের মানের থেকে ছোট হয়। এখন আমরা Max-Heap এবং Min-Heap এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন দেখবো।

Max-Heap এর ইমপ্লিমেন্টেশন

Max-Heap ইমপ্লিমেন্ট করার জন্য ইনসার্ট (insert), এক্সট্র্যাক্ট (extract) এবং হিপিফাই (heapify) ফাংশন প্রয়োজন হয়।

Max-Heap এর সি কোড:

#include <stdio.h>

#define MAX 10
int heap[MAX];
int size = 0;

// Swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify the tree to maintain Max-Heap property
void heapify(int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // Left child is larger
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }

    // Right child is larger
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }

    // If largest is not root
    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        heapify(largest);
    }
}

// Insert an element into the heap
void insert(int value) {
    if (size == MAX) {
        printf("Heap Overflow\n");
        return;
    }

    heap[size++] = value;
    int i = size - 1;

    // Move the inserted value to its correct position
    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Extract the root (max) element
int extractMax() {
    if (size == 0) {
        printf("Heap Underflow\n");
        return -1;
    }

    int max = heap[0];
    heap[0] = heap[--size];
    heapify(0);
    
    return max;
}

// Print the heap array
void printHeap() {
    for (int i = 0; i < size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

int main() {
    insert(10);
    insert(20);
    insert(5);
    insert(30);
    insert(40);

    printf("Max-Heap: ");
    printHeap();

    printf("Extract Max: %d\n", extractMax());

    printf("Max-Heap after extraction: ");
    printHeap();

    return 0;
}

Min-Heap এর ইমপ্লিমেন্টেশন

Min-Heap-এ প্রতিটি নোডের মান তার সন্তানের মানের থেকে ছোট হয়। এটি Max-Heap এর বিপরীত।

Min-Heap এর সি কোড:

#include <stdio.h>

#define MAX 10
int heap[MAX];
int size = 0;

// Swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify the tree to maintain Min-Heap property
void heapify(int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // Left child is smaller
    if (left < size && heap[left] < heap[smallest]) {
        smallest = left;
    }

    // Right child is smaller
    if (right < size && heap[right] < heap[smallest]) {
        smallest = right;
    }

    // If smallest is not root
    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        heapify(smallest);
    }
}

// Insert an element into the heap
void insert(int value) {
    if (size == MAX) {
        printf("Heap Overflow\n");
        return;
    }

    heap[size++] = value;
    int i = size - 1;

    // Move the inserted value to its correct position
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Extract the root (min) element
int extractMin() {
    if (size == 0) {
        printf("Heap Underflow\n");
        return -1;
    }

    int min = heap[0];
    heap[0] = heap[--size];
    heapify(0);

    return min;
}

// Print the heap array
void printHeap() {
    for (int i = 0; i < size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

int main() {
    insert(10);
    insert(20);
    insert(5);
    insert(30);
    insert(40);

    printf("Min-Heap: ");
    printHeap();

    printf("Extract Min: %d\n", extractMin());

    printf("Min-Heap after extraction: ");
    printHeap();

    return 0;
}

Max-Heap এবং Min-Heap এর মধ্যে পার্থক্য

• Max-Heap:
  • রুট নোড সর্বোচ্চ মান ধারণ করে।
  • প্রতিটি পিতার মান তার সন্তানের মানের থেকে বড় থাকে।
• Min-Heap:
  • রুট নোড সর্বনিম্ন মান ধারণ করে।
  • প্রতিটি পিতার মান তার সন্তানের মানের থেকে ছোট থাকে।

সারসংক্ষেপ

• Max-Heap এবং Min-Heap দুটি আলাদা হিপ গঠন যা সি প্রোগ্রামিং ভাষায় কার্যকরীভাবে ব্যবহার করা যায়।
• Max-Heap সর্বোচ্চ মানের উপাদান বের করার জন্য ব্যবহৃত হয়, যেখানে Min-Heap সর্বনিম্ন মানের উপাদান বের করার জন্য ব্যবহৃত হয়।
• এই দুটি হিপ গঠন ইনসার্ট, এক্সট্র্যাক্ট, এবং হিপিফাই অপারেশন ব্যবহার করে পরিচালিত হয়।